High functional coherence in k-partite protein cliques of protein interaction networks

摘要

We introduce a new topological concept called to study protein interaction (PPI) networks. In particular, we examine functional coherence of proteins in -partite protein cliques. A -partite protein clique is a -partite maximal clique comprising two or more nonoverlapping protein subsets between any two of which full interactions are exhibited. In the detection of PPI’s -partite maximal cliques, we propose to transform PPI networks into induced -partite graphs with proteins as vertices where edges only exist among the graph’s partites. Then, we present a -partite maximal clique mining (MaCMik) algorithm to enumerate-partite maximal cliques from -partite graphs. Our MaCMik algorithm is applied to a yeast PPI network. We observe that there does exist interesting and unusually high functional coherence in -partite protein cliques—most proteins in-partite protein cliques, especially those in the same partites, share the same functions. Therefore, the idea of -partite protein cliques suggests a novel approach to characterizing PPI networks, and may help function prediction for unknown proteins.